package cn.cxq.learning.disjoint_set;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;


/**
 * 牛客题霸-全部题目
 * 数组中的最长连续子序列
 * 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M 热度指数：10310
 * 本题知识点： 并查集 数组
 *  算法知识视频讲解
 * 题目描述
 * 给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
 * 示例1
 * 输入
 * 复制
 * [100,4,200,1,3,2]
 * 返回值
 * 复制
 * 4
 * 示例2
 * 输入
 * 复制
 * [1,1,1]
 * 返回值
 * 复制
 * 1
 * 备注:
 * 1 \leq n \leq 10^51≤n≤10
 * 5
 *
 * 1 \leq arr_i \leq 10^81≤arr
 * i
 * ​
 *  ≤10
 * 8
 *
 *  关联企业
 * 字节跳动腾讯网易阿里巴巴
 *  关联职位
 * 研发测试算法
 */
public class MLS {

//    public int MLS (int[] arr) {
//        // write code here
//
//        Arrays.sort(arr);
//
//        int maxSize = 0;
//        int temp = 1;
//
//        for (int i = 0; i < arr.length - 1; i++) {
//
//            if (arr[i] == arr[i + 1]) {
//                continue;
//            } else if (arr[i] + 1 != arr[i + 1]) {
//                maxSize = Math.max(maxSize, temp);
//                temp = 1;
//            } else {
//                temp++;
//            }
//        }
//
//        maxSize = Math.max(maxSize, temp);
//
//        return maxSize;
//    }

    // 并查集解题 ：
    public int MLS (int[] arr) {
        // disjoint set
        DisjointSet dSet = new DisjointSet(arr);

        for (Integer node : dSet.nodes) {
            dSet.union(node, node - 1);
        }

        return dSet.maxSize;
    }
}

class DisjointSet {

    HashSet<Integer> nodes = new HashSet<>();
    HashMap<Integer, Integer> parent = new HashMap<>();
    HashMap<Integer, Integer> size = new HashMap<>();
    int maxSize = 1;

    public DisjointSet(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            parent.put(arr[i], arr[i]);
            size.put(arr[i], 1);
            nodes.add(arr[i]);
        }
    }

    public void union(int node1, int node2) {

        if (!nodes.contains(node2)) {
            return;
        }

        int root1 = find(node1);
        int root2 = find(node2);

        if (size.get(root1) > size.get(root2)) {
            parent.put(root2, root1);
            size.put(root1, size.get(root1) + size.get(root2));
            maxSize = Math.max(maxSize, size.get(root1));
        } else {
            parent.put(root1, root2);
            size.put(root2, size.get(root1) + size.get(root2));
            maxSize = Math.max(maxSize, size.get(root2));
        }
    }

    // 寻找树的根节点
    public int find(int node) {
        while(parent.get(node) != node) {
            int temp = parent.get(node);
            node = temp;
        }

        return node;
    }
}